package problem;

public class S_110 {
    //给定一个平衡二叉树，判断是否是高度平衡的二叉树
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    //1.递归
    class Solution {
        public boolean isBalanced(TreeNode root) {
            if(root==null)  return true;
            int left=depth(root.left);
            int right=depth(root.right);
            if(Math.abs(left-right)<2) return isBalanced(root.left)&&isBalanced(root.right);
            return false;
        }
        private int depth(TreeNode root){
            if(root==null) return 0;
            int left=depth(root.left);
            int right=depth(root.right);
            return Math.max(left,right)+1;
        }
    }
    //2.提前阻断法
    class Solution1{
        public boolean isBalanced(TreeNode root) {
            return depth(root) != -1;
        }

        private int depth(TreeNode root) {
            if (root == null) return 0;
            int left = depth(root.left);
            if(left == -1) return -1;
            int right = depth(root.right);
            if(right == -1) return -1;
            return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
        }
    }
}
